home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / sbwbs.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  13.8 KB  |  550 lines
  1. /* Copyright (C) 1994, 1995, 1998, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: sbwbs.c,v 1.2 2000/09/19 19:00:48 lpd Exp $ */
  20. /* Burrows/Wheeler block sorting compression filters */
  21. #include "stdio_.h"
  22. #include "memory_.h"
  23. #include <stdlib.h>        /* for qsort */
  24. #include "gdebug.h"
  25. #include "strimpl.h"
  26. #include "sfilter.h"
  27. #include "sbwbs.h"
  28.  
  29. /* ------ Common code for streams that buffer a block ------ */
  30.  
  31. private_st_buffered_state();
  32.  
  33. /* Initialize */
  34. private void
  35. s_buffered_set_defaults(stream_state * st)
  36. {
  37.     stream_buffered_state *const ss = (stream_buffered_state *) st;
  38.  
  39.     /* Clear pointers */
  40.     ss->buffer = 0;
  41. }
  42. private int
  43. s_buffered_no_block_init(stream_state * st)
  44. {
  45.     stream_buffered_state *const ss = (stream_buffered_state *) st;
  46.  
  47.     ss->buffer = 0;
  48.     ss->filling = true;
  49.     ss->bpos = 0;
  50.     return 0;
  51. }
  52. private int
  53. s_buffered_block_init(stream_state * st)
  54. {
  55.     stream_buffered_state *const ss = (stream_buffered_state *) st;
  56.  
  57.     s_buffered_no_block_init(st);
  58.     ss->buffer = gs_alloc_bytes(st->memory, ss->BlockSize, "buffer");
  59.     if (ss->buffer == 0)
  60.     return ERRC;
  61. /****** WRONG ******/
  62.     return 0;
  63. }
  64.  
  65. /* Continue filling the buffer if needed. */
  66. /* Return 0 if the buffer isn't full yet, 1 if it is full or if */
  67. /* we reached the end of input data. */
  68. /* In the latter case, also set filling = false. */
  69. /* Note that this procedure doesn't take pw as an argument. */
  70. private int
  71. s_buffered_process(stream_state * st, stream_cursor_read * pr, bool last)
  72. {
  73.     stream_buffered_state *const ss = (stream_buffered_state *) st;
  74.     register const byte *p = pr->ptr;
  75.     const byte *rlimit = pr->limit;
  76.     uint count = rlimit - p;
  77.     uint left = ss->bsize - ss->bpos;
  78.  
  79.     if (!ss->filling)
  80.     return 1;
  81.     if (left < count)
  82.     count = left;
  83.     if_debug3('w', "[w]buffering %d bytes to position %d, last = %s\n",
  84.           count, ss->bpos, (last ? "true" : "false"));
  85.     memcpy(ss->buffer + ss->bpos, p + 1, count);
  86.     pr->ptr = p += count;
  87.     ss->bpos += count;
  88.     if (ss->bpos == ss->bsize || (p == rlimit && last)) {
  89.     ss->filling = false;
  90.     return 1;
  91.     }
  92.     return 0;
  93. }
  94.  
  95. /* Release */
  96. private void
  97. s_buffered_release(stream_state * st)
  98. {
  99.     stream_buffered_state *const ss = (stream_buffered_state *) st;
  100.  
  101.     gs_free_object(st->memory, ss->buffer, "buffer");
  102. }
  103.  
  104. /* ------ Common code for Burrows/Wheeler block sorting filters ------ */
  105.  
  106. private_st_BWBS_state();
  107. private void s_BWBS_release(P1(stream_state *));
  108.  
  109. /* Set default parameter values (actually, just clear pointers). */
  110. private void
  111. s_BWBS_set_defaults(stream_state * st)
  112. {
  113.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  114.  
  115.     s_buffered_set_defaults(st);
  116.     ss->offsets = 0;
  117. }
  118.  
  119. /* Initialize */
  120. private int
  121. bwbs_init(stream_state * st, uint osize)
  122. {
  123.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  124.     int code;
  125.  
  126.     ss->bsize = ss->BlockSize;
  127.     code = s_buffered_block_init(st);
  128.     if (code != 0)
  129.     return code;
  130.     ss->offsets = (void *)gs_alloc_bytes(st->memory, osize,
  131.                      "BWBlockSort offsets");
  132.     if (ss->offsets == 0) {
  133.     s_BWBS_release(st);
  134.     return ERRC;
  135. /****** WRONG ******/
  136.     }
  137.     ss->I = -1;            /* haven't read I yet */
  138.     return 0;
  139. }
  140.  
  141. /* Release the filter. */
  142. private void
  143. s_BWBS_release(stream_state * st)
  144. {
  145.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  146.  
  147.     gs_free_object(st->memory, ss->offsets, "BWBlockSort offsets");
  148.     s_buffered_release(st);
  149. }
  150.  
  151. /* ------ BWBlockSortEncode ------ */
  152.  
  153. /* Initialize */
  154. private int
  155. s_BWBSE_init(stream_state * st)
  156. {
  157.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  158.  
  159.     return bwbs_init(st, ss->BlockSize * sizeof(int));
  160. }
  161.  
  162. /* Compare two rotated strings for sorting. */
  163. private stream_BWBS_state *bwbs_compare_ss;
  164. private int
  165. bwbs_compare_rotations(const void *p1, const void *p2)
  166. {
  167.     const byte *buffer = bwbs_compare_ss->buffer;
  168.     const byte *s1 = buffer + *(const int *)p1;
  169.     const byte *s2 = buffer + *(const int *)p2;
  170.     const byte *start1;
  171.     const byte *end;
  172.     int swap;
  173.  
  174.     if (*s1 != *s2)
  175.     return (*s1 < *s2 ? -1 : 1);
  176.     if (s1 < s2)
  177.     swap = 1;
  178.     else {
  179.     const byte *t = s1;
  180.  
  181.     s1 = s2;
  182.     s2 = t;
  183.     swap = -1;
  184.     }
  185.     start1 = s1;
  186.     end = buffer + bwbs_compare_ss->N;
  187.     for (s1++, s2++; s2 < end; s1++, s2++)
  188.     if (*s1 != *s2)
  189.         return (*s1 < *s2 ? -swap : swap);
  190.     s2 = buffer;
  191.     for (; s1 < end; s1++, s2++)
  192.     if (*s1 != *s2)
  193.         return (*s1 < *s2 ? -swap : swap);
  194.     s1 = buffer;
  195.     for (; s1 < start1; s1++, s2++)
  196.     if (*s1 != *s2)
  197.         return (*s1 < *s2 ? -swap : swap);
  198.     return 0;
  199. }
  200. /* Sort the strings. */
  201. private void
  202. bwbse_sort(const byte * buffer, uint * indices, int N)
  203. {
  204.     offsets_full Cs;
  205.  
  206. #define C Cs.v
  207.     /* Sort the strings.  We start with a radix sort. */
  208.     uint sum = 0, j, ch;
  209.  
  210.     memset(C, 0, sizeof(Cs));
  211.     for (j = 0; j < N; j++)
  212.     C[buffer[j]]++;
  213.     for (ch = 0; ch <= 255; ch++) {
  214.     sum += C[ch];
  215.     C[ch] = sum - C[ch];
  216.     }
  217.     for (j = 0; j < N; j++)
  218.     indices[C[buffer[j]]++] = j;
  219.     /* Now C[ch] = the number of strings that start */
  220.     /* with a character less than or equal to ch. */
  221.     sum = 0;
  222.     /* qsort each bucket produced by the radix sort. */
  223.     for (ch = 0; ch <= 255; sum = C[ch], ch++)
  224.     qsort(indices + sum, C[ch] - sum,
  225.           sizeof(*indices),
  226.           bwbs_compare_rotations);
  227. #undef C
  228. }
  229.  
  230. /* Encode a buffer */
  231. private int
  232. s_BWBSE_process(stream_state * st, stream_cursor_read * pr,
  233.         stream_cursor_write * pw, bool last)
  234. {
  235.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  236.     register byte *q = pw->ptr;
  237.     byte *wlimit = pw->limit;
  238.     uint wcount = wlimit - q;
  239.     uint *indices = ss->offsets;
  240.  
  241.     if (ss->filling) {
  242.     int status, j, N;
  243.     byte *buffer = ss->buffer;
  244.     if (wcount < sizeof(int) * 2)
  245.             return 1;
  246.  
  247.     /* Continue filling the buffer. */
  248.     status = s_buffered_process(st, pr, last);
  249.     if (!status)
  250.         return 0;
  251.     ss->N = N = ss->bpos;
  252.     /* We reverse the string before encoding it, */
  253.     /* so it will come out of the decoder correctly. */
  254.     for (j = N / 2 - 1; j >= 0; j--) {
  255.         byte *p0 = &buffer[j];
  256.         byte *p1 = &buffer[N - 1 - j];
  257.         byte b = *p0;
  258.  
  259.         *p0 = *p1;
  260.         *p1 = b;
  261.     }
  262.     /* Save st in a static, because that's the only way */
  263.     /* we can pass it to the comparison procedure (ugh). */
  264.     bwbs_compare_ss = ss;
  265.     /* Sort the strings. */
  266.     bwbse_sort(buffer, indices, N);
  267.     /* Find the unrotated string. */
  268.     for (j = 0; j < N; j++)
  269.         if (indices[j] == 0) {
  270.         ss->I = j;
  271.         break;
  272.         }
  273.     for (j = sizeof(int); --j >= 0;)
  274.         *++q = (byte) (N >> (j * 8));
  275.     for (j = sizeof(int); --j >= 0;)
  276.         *++q = (byte) (ss->I >> (j * 8));
  277.     ss->bpos = 0;
  278.     }
  279.     /* We're reading out of the buffer, writing the permuted string. */
  280.     while (q < wlimit && ss->bpos < ss->N) {
  281.     int i = indices[ss->bpos++];
  282.  
  283.     *++q = ss->buffer[(i == 0 ? ss->N - 1 : i - 1)];
  284.     }
  285.     if (ss->bpos == ss->N) {
  286.     ss->filling = true;
  287.     ss->bpos = 0;
  288.     }
  289.     pw->ptr = q;
  290.     if (q == wlimit)
  291.     return 1;
  292.     return 0;
  293. }
  294.  
  295. /* Stream template */
  296. const stream_template s_BWBSE_template = {
  297.     &st_BWBS_state, s_BWBSE_init, s_BWBSE_process, sizeof(int) * 2, 1,
  298.     s_BWBS_release, s_BWBS_set_defaults
  299. };
  300.  
  301. /* ------ BWBlockSortDecode ------ */
  302.  
  303. #define SHORT_OFFSETS
  304.  
  305. #ifdef SHORT_OFFSETS
  306.  
  307. /*
  308.  * Letting S[0..N-1] be the data block before depermutation, we need
  309.  * a table P[0..N-1] that maps the index i to O(S[i],i), where O(c,i) is
  310.  * the number of occurrences of c in S before position i.
  311.  * We observe that for a fixed c, O(c,i) is monotonic with i,
  312.  * and falls in the range 0 .. i; consequently, if 0 <= i <= j,
  313.  * 0 <= O(c,j) - O(c,i) <= j - i.  Proceeding from this observation,
  314.  * rather than allocate an entire int to each entry of P,
  315.  * we construct three tables as follows:
  316.  *      P2[k,c] = O(c,k*65536) for k = 0 .. (N-1)/65536;
  317.  *              each entry requires an int.
  318.  *      P1[k,c] = O(c,k*4096) - P2[k/16,c] for k = 0 .. (N-1)/4096;
  319.  *              each entry falls in the range 0 .. 15*4096 and hence
  320.  *              requires 16 bits.
  321.  *      P0[i] = O(S[i],i) - P1[i/4096,S[i]] for i = 0 .. N-1;
  322.  *              each entry falls in the range 0 .. 4095 and hence
  323.  *              requires 12 bits.
  324.  * Since the value we need in the decompression loop is actually
  325.  * P[i] + C[S[i]], where C[c] is the sum of O(0,N) ... O(c-1,N),
  326.  * we add C[c] into P2[k,c] for all k.
  327.  */
  328.                             /*typedef struct { uint v[256]; } offsets_full; *//* in sbwbs.h */
  329. typedef struct {
  330.     bits16 v[256];
  331. } offsets_4k;
  332.  
  333. #if arch_sizeof_int > 2
  334. #  define ceil_64k(n) (((n) + 0xffff) >> 16)
  335. #else
  336. #  define ceil_64k(n) 1
  337. #endif
  338. #define ceil_4k(n) (((n) + 0xfff) >> 12)
  339. #define offset_space(bsize)\
  340.   (ceil_64k(bsize) * sizeof(offsets_full) +\
  341.    ceil_4k(bsize) * sizeof(offsets_4k) +\
  342.    ((bsize + 1) >> 1) * 3)
  343.  
  344. #else /* !SHORT_OFFSETS */
  345.  
  346. #define offset_space(bsize)\
  347.   (bsize * sizeof(int))
  348.  
  349. #endif /* (!)SHORT_OFFSETS */
  350.  
  351. /* Initialize */
  352. private int
  353. s_BWBSD_init(stream_state * st)
  354. {
  355.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  356.     uint bsize = ss->BlockSize;
  357.  
  358.     return bwbs_init(st, offset_space(bsize));
  359. }
  360.  
  361. /* Construct the decoding tables. */
  362.  
  363. #ifdef SHORT_OFFSETS
  364.  
  365. private void
  366. bwbsd_construct_offsets(stream_BWBS_state * sst, offsets_full * po64k,
  367.             offsets_4k * po4k, byte * po1, int N)
  368. {
  369.     offsets_full Cs;
  370.  
  371. #define C Cs.v
  372.     uint i1;
  373.     byte *b = sst->buffer;
  374.     offsets_full *p2 = po64k - 1;
  375.     offsets_4k *p1 = po4k;
  376.     byte *p0 = po1;
  377.  
  378.     memset(C, 0, sizeof(Cs));
  379.     for (i1 = 0; i1 < ceil_4k(N); i1++, p1++) {
  380.     int j;
  381.  
  382.     if (!(i1 & 15))
  383.         *++p2 = Cs;
  384.     for (j = 0; j < 256; j++)
  385.         p1->v[j] = C[j] - p2->v[j];
  386.     j = (N + 1 - (i1 << 12)) >> 1;
  387.     if (j > 4096 / 2)
  388.         j = 4096 / 2;
  389.     for (; j > 0; j--, b += 2, p0 += 3) {
  390.         byte b0 = b[0];
  391.         uint d0 = C[b0]++ - (p1->v[b0] + p2->v[b0]);
  392.         byte b1 = b[1];
  393.         uint d1 = C[b1]++ - (p1->v[b1] + p2->v[b1]);
  394.  
  395.         p0[0] = d0 >> 4;
  396.         p0[1] = (byte) ((d0 << 4) + (d1 >> 8));
  397.         p0[2] = (byte) d1;
  398.     }
  399.     }
  400.     /* If the block length is odd, discount the extra byte. */
  401.     if (N & 1)
  402.     C[sst->buffer[N]]--;
  403.     /* Compute the cumulative totals in C. */
  404.     {
  405.     int sum = 0, ch;
  406.  
  407.     for (ch = 0; ch <= 255; ch++) {
  408.         sum += C[ch];
  409.         C[ch] = sum - C[ch];
  410.     }
  411.     }
  412.     /* Add the C values back into the 64K table, */
  413.     /* which saves an addition of C[b] in the decoding loop. */
  414.     {
  415.     int i2, ch;
  416.  
  417.     for (p2 = po64k, i2 = ceil_64k(N); i2 > 0; p2++, i2--)
  418.         for (ch = 0; ch < 256; ch++)
  419.         p2->v[ch] += C[ch];
  420.     }
  421. #undef C
  422. }
  423.  
  424. #else /* !SHORT_OFFSETS */
  425.  
  426. private void
  427. bwbsd_construct_offsets(stream_BWBS_state * sst, int *po, int N)
  428. {
  429.     offsets_full Cs;
  430.  
  431. #define C Cs.v
  432.     uint i;
  433.     byte *b = sst->buffer;
  434.     int *p = po;
  435.  
  436.     memset(C, 0, sizeof(Cs));
  437.     for (i = 0; i < N; i++, p++, b++)
  438.     *p = C[*b]++;
  439.     /* Compute the cumulative totals in C. */
  440.     {
  441.     int sum = 0, ch;
  442.  
  443.     for (ch = 0; ch <= 255; ch++) {
  444.         sum += C[ch];
  445.         C[ch] = sum - C[ch];
  446.     }
  447.     }
  448.     /* Add the C values back into the offsets. */
  449.     for (i = 0, b = sst->buffer, p = po; i < N; i++, b++, p++)
  450.     *p += C[*b];
  451. #undef C
  452. }
  453.  
  454. #endif /* (!)SHORT_OFFSETS */
  455.  
  456. /* Decode a buffer */
  457. private int
  458. s_BWBSD_process(stream_state * st, stream_cursor_read * pr,
  459.         stream_cursor_write * pw, bool last)
  460. {
  461.     stream_BWBS_state *const ss = (stream_BWBS_state *) st;
  462.     register const byte *p = pr->ptr;
  463.     const byte *rlimit = pr->limit;
  464.     uint count = rlimit - p;
  465.     register byte *q = pw->ptr;
  466.     byte *wlimit = pw->limit;
  467.  
  468. #ifdef SHORT_OFFSETS
  469.     uint BlockSize = ss->BlockSize;
  470.     offsets_full *po64k = ss->offsets;
  471.     offsets_4k *po4k = (offsets_4k *) (po64k + ceil_64k(BlockSize));
  472.     byte *po1 = (byte *) (po4k + ceil_4k(BlockSize));
  473.  
  474. #else /* !SHORT_OFFSETS */
  475.     int *po = ss->offsets;
  476.  
  477. #endif /* (!)SHORT_OFFSETS */
  478.  
  479.     if (ss->I < 0) {        /* Read block parameters */
  480.     int I, N, j;
  481.     if (count < sizeof(int) * 2)
  482.             return 0;
  483.     for (N = 0, j = 0; j < sizeof(int); j++)
  484.  
  485.         N = (N << 8) + *++p;
  486.     for (I = 0, j = 0; j < sizeof(int); j++)
  487.  
  488.         I = (I << 8) + *++p;
  489.     ss->N = N;
  490.     ss->I = I;
  491.     if_debug2('w', "[w]N=%d I=%d\n", N, I);
  492.     pr->ptr = p;
  493.     if (N < 0 || N > ss->BlockSize || I < 0 || I >= N)
  494.         return ERRC;
  495.     if (N == 0)
  496.         return EOFC;
  497.     count -= sizeof(int) * 2;
  498.  
  499.     ss->bpos = 0;
  500.     ss->bsize = N;
  501.     }
  502.     if (ss->filling) {        /* Continue filling the buffer. */
  503.     if (!s_buffered_process(st, pr, last))
  504.         return 0;
  505.     /* Construct the inverse sort order. */
  506. #ifdef SHORT_OFFSETS
  507.     bwbsd_construct_offsets(ss, po64k, po4k, po1, ss->bsize);
  508. #else /* !SHORT_OFFSETS */
  509.     bwbsd_construct_offsets(ss, po, ss->bsize);
  510. #endif /* (!)SHORT_OFFSETS */
  511.     ss->bpos = 0;
  512.     ss->i = ss->I;
  513.     }
  514.     /* We're reading out of the buffer. */
  515.     while (q < wlimit && ss->bpos < ss->bsize) {
  516.     int i = ss->i;
  517.     byte b = ss->buffer[i];
  518.  
  519. #ifdef SHORT_OFFSETS
  520.     uint d;
  521.     const byte *pd = &po1[(i >> 1) + i];
  522.  
  523.     *++q = b;
  524.     if (!(i & 1))
  525.         d = ((uint) pd[0] << 4) + (pd[1] >> 4);
  526.     else
  527.         d = ((pd[0] & 0xf) << 8) + pd[1];
  528.     ss->i = po64k[i >> 16].v[b] + po4k[i >> 12].v[b] + d;
  529. #else /* !SHORT_OFFSETS */
  530.     *++q = b;
  531.     ss->i = po[i];
  532. #endif /* (!)SHORT_OFFSETS */
  533.     ss->bpos++;
  534.     }
  535.     if (ss->bpos == ss->bsize) {
  536.     ss->I = -1;
  537.     ss->filling = true;
  538.     }
  539.     pw->ptr = q;
  540.     if (q == wlimit)
  541.     return 1;
  542.     return 0;
  543. }
  544.  
  545. /* Stream template */
  546. const stream_template s_BWBSD_template = {
  547.     &st_BWBS_state, s_BWBSD_init, s_BWBSD_process, 1, sizeof(int) * 2,
  548.     s_BWBS_release, s_BWBS_set_defaults
  549. };
  550.